{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use $M$ to represent the kernal matrix, so in general\n",
    "\n",
    "$$\n",
    "u^TMu = \\sum_{i,j}^{m} u_i u_j K(x^{(i)}, x^{(j)})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j (K_1(x^{(i)}, x^{(j)}) + K_2(x^{(i)}, x^{(j)})) \\\\\n",
    "      &= \\sum_{i,j}^{m} (u_i u_j K_1(x^{(i)}, x^{(j)})) + \\sum_{i,j}^{m} (u_i u_j K_2(x^{(i)}, x^{(j)})) \\\\\n",
    "      &\\ge 0\n",
    "\\end{align*}\n",
    "so $K$ is a kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j (K_1(x^{(i)}, x^{(j)}) - K_2(x^{(i)}, x^{(j)})) \\\\\n",
    "      &= \\sum_{i,j}^{m} (u_i u_j K_1(x^{(i)}, x^{(j)})) - \\sum_{i,j}^{m} (u_i u_j K_2(x^{(i)}, x^{(j)})) \\\\\n",
    "\\end{align*}\n",
    "\n",
    "doesn't necessarily equals 0, so $K$ is not a kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given $a \\in \\mathbb{R}$ and $a > 0$\n",
    "\n",
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j aK_1(x^{(i)}, x^{(j)}) \\\\\n",
    "      &\\ge 0\n",
    "\\end{align*}\n",
    "\n",
    "so $K$ is a kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given $a \\in \\mathbb{R}$ and $a > 0$\n",
    "\n",
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j (-a)K_1(x^{(i)}, x^{(j)}) \\\\\n",
    "      &\\le 0\n",
    "\\end{align*}\n",
    "\n",
    "so $K$ is not a kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $K_1$ and $K_2$ are both kernels, there are functions $\\phi_1: \\mathbb{R}^n \\rightarrow \\mathbb{R^{d_1}}$ and $\\phi_2:  \\mathbb{R}^n \\rightarrow \\mathbb{R^{d_2}}$ that meet the following equalities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "K_1(x, z) &= \\phi_1(x)^T \\phi_1(z) \\\\\n",
    "K_2(x, z) &= \\phi_2(x)^T \\phi_2(z) \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "K(x, z) \n",
    "&= K_1(x, z) K_2(x, z) \\\\\n",
    "&= \\phi_1(x)^T \\phi_1(z) \\phi_2(x)^T \\phi_2(z) \\\\\n",
    "&= \\sum_i^{d_1} \\phi_1(x)_{i}\\phi_1(z)_{i} \\sum_j^{d_2}\\phi_2(x)_j\\phi_2(z)_j \\\\\n",
    "&= \\sum_i^{d_1}\\sum_j^{d_2}\\phi_1(x)_{i}\\phi_1(z)_{i}\\phi_2(x)_j\\phi_2(z)_j \\\\\n",
    "&= \\sum_i^{d_1}\\sum_j^{d_2} \\Big(\\phi_1(x)_{i}\\phi_2(x)_j \\Big) \\Big(\\phi_1(z)_{i}\\phi_2(z)_j\\Big) \\\\\n",
    "&= \\text{flat}\\Big(\\phi_1(x)\\phi_2(x)^T\\Big) \\text{flat}\\Big(\\phi_1(z)\\phi_2(z)^T\\Big) \\\\\n",
    "&= \\phi_3(x)^T\\phi_3(z)\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where $\\phi_3$ is a $\\mathbb{R}^n \\rightarrow \\mathbb{R^{d_1 d_2}}$ function. Therefore, $K_3$ is a kernel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\text{flat}$ just means to flatten the matrix returned by outer product of two vectors, see https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.flatten.html for an example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Caveat**: $K_1(x, z) K_2(x, z)$ is NOT a matrix multiplication. Thank you @Vrroom for bringing it up (https://github.com/zyxue/stanford-cs229/issues/22)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reference: https://stats.stackexchange.com/questions/48509/proof-of-closeness-of-kernel-functions-under-pointwise-product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "u^TMu\n",
    "&= \\sum_{i,j}^{m} u_i u_j f(x^{(i)})f(x^{(j)}) \\\\\n",
    "&= \\bigg( u_1 f(x^{(1)}) + u_2 f(x^{(2)}) + \\cdots + u_m f(x^{(m)}) \\bigg)^2 \\\\\n",
    "& = \\sum_{i}^{m}\\bigg( u_i f(x^{(i)}) \\bigg)^2 \\\\\n",
    "&\\ge 0\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, $K$ is a kernel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j K_3(\\phi(x^{(i)}), \\phi(x^{(j)}))\\\\\n",
    "      &\\ge 0\n",
    "\\end{align*}\n",
    "\n",
    "it appears that $\\phi$ doesn't matter as long as $K_3$ is a valid kernel. It's equivalent to transform all input first with $\\phi$ and then run SVM with $K_3$ as a kernel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given\n",
    "\n",
    "\\begin{align*}\n",
    "u^TMu &= \\sum_{i,j}^{m} u_i u_j K_1(x^{(i)}, x^{(j)})\\\\\n",
    "      &\\ge 0\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "using (a), (c), (e) shown above,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "u^TMu\n",
    "&= \\sum_{i,j}^{m} u_i u_j p(K_1(x^{(i)}, x^{(j)})) \\\\\n",
    "&= \\sum_{i,j}^{m} u_i u_j \\bigg( \\sum_{k} \\alpha_k \\big(K_1(x^{(i)}, x^{(j)})\\big)^k\\bigg) \\\\\n",
    "&\\ge 0\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, $K$ is a kernel."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
